package com.tim.test.leetcode.simulation.huawei;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author
 * @Title:
 * @Package
 * @date 2023/6/10 15:04
 * @Description:
 */
public class Simulation2 {
    public static void main(String[] args) {
        Simulation2 s = new Simulation2();
        Object r=null;
        s.minSwapTimes();
//        s.minStep();
//        s.memoryAllocate();
//        s.dicTree();
        System.out.println(r);
    }

    // 小于k的值在同一侧
    // 类同快速排序，先检索左右分别进行一次；取最小值
    // 定位首个小于k的值为起始点；双指针
    public void minSwapTimes(){
        int k = -1;
        String str = "7 3 1 3 3 1 1 7 8 4 0 6 7";
        Integer[] nums = Arrays.stream(str.trim().split("\\s+"))
                .map(Integer::valueOf)
                .toArray(Integer[]::new);
        int length = nums.length;
        int leftStart=-1, leftTimes=0, rightEnd=length-1;
        for (int i = 0; i < length; i++) {
            if(nums[i]<k){
                leftStart = i;
                break;
            }
        }
        for (int i = leftStart+1; i < length && rightEnd>i; i++) {
            if(nums[i]>=k){
                while(rightEnd>i && nums[rightEnd]>=k){
                    // 右侧找到小于k的值
                    rightEnd--;
                }
                if(nums[rightEnd]<k){
                    leftTimes++;// 找到值，交换次数+1
                }
                rightEnd--;
            }
        }
        int rightStart=-1, rightTimes=0, leftEnd=0;
        for (int i = length-1; i > -1; i--) {
            if(nums[i]<k){
                rightStart = i;
                break;
            }
        }

        for (int i = rightStart-1; i >-1 && leftEnd<i; i--) {
            if(nums[i]>=k){
                while(leftEnd<i && nums[leftEnd]>=k){
                    // 右侧找到小于k的值
                    leftEnd++;
                }
                if(nums[leftEnd]<k){
                    rightTimes++;// 找到值，交换次数+1
                }
                leftEnd++;
            }
        }


        System.out.println(Math.min(leftTimes, rightTimes));
    }

    // 最少步数。
    // 尽可能的走大步，余量通过大小步调节
    public void minStep(){
        int distance = 3;
        int step3 = distance/3;
        int left = distance%3;
        int step2 = 0;
        if(left==1){
            step2 = step3==0 ? 1 : 2;
            step3 = step3==0 ? 1 : step3-1;
        }else if(left==2){
            step2 = 1;
        }

        System.out.println(step2+step3);

    }

    // 内存分配
    // int[]，index为资源大小，val为资源数量。注意数组大小为max(index)+1
    // 对申请大小a的分配，向后检索
    public void memoryAllocate(){
        String info = "64:2,128:1,32:4,1:128";
        String info2 = "50,36,64,128,127";
        int[] sources = new int[1025];// 资源值最大1024
        Arrays.fill(sources, 0);
        Arrays.stream(info.split(","))
                .forEach(str->{
                    String[] split = str.split(":");
                    sources[Integer.valueOf(split[0])]+=Integer.valueOf(split[1]);
                });
        Integer[] applys = Arrays.stream(info2.split(","))
                .map(Integer::valueOf)
                .toArray(Integer[]::new);

        List<Boolean> list = new ArrayList<>();
        for (int i = 0; i < applys.length; i++) {
            Integer apply = applys[i];
            boolean flag = false;
            for (int j = apply; j < sources.length; j++) {
                if(sources[j]>0){
                    flag = true;
                    sources[j]--;
                    break;
                }
            }
            list.add(flag);
        }
        System.out.println(list.stream().map(Objects::toString).collect(Collectors.joining(",")));
    }

    // 字典树
    // 构建字典树，Map<String, Node>，查找到isEnd=true的匹配
    // bfs遍历输出
    public void dicTree(){
        String info = "a 6 a ab abd adb abc abcd";
        String[] split = info.trim().split("\\s+");
        String pre = split[0];
        Node root = new Node(null);
        root.isEnd=false;
        int end = Math.min(Integer.valueOf(split[1]), split.length);
        for (int i = 2; i < end+2; i++) {
            String str = split[i];
            Node temp = root;
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                if(!temp.children.containsKey(c)){
                    Node node = new Node(c);
                    temp.children.put(c, node);
                }
                temp = temp.children.get(c);
                if(!temp.isEnd && j==str.length()-1){
                    temp.isEnd = true;
                }
            }
        }

        Node dest = root;
        for (int i = 0; i < pre.length(); i++) {
            char c = pre.charAt(i);
            if(!dest.children.containsKey(c)){
                System.out.println(-1);
                return;
            }
            dest = dest.children.get(c);
        }
        System.out.println(pre);
        Map<String, Collection<Node>> preMap = new HashMap<>();
        preMap.put(pre, dest.children.values());
        while(!preMap.isEmpty()){
            Map<String, Collection<Node>> tempMap = new HashMap<>();
            for (String preStr : preMap.keySet()){
                Collection<Node> nodes = preMap.get(preStr);
                for(Node node : nodes){
                    if(node.isEnd){
                        System.out.println(preStr+node.c);
                    }
                    tempMap.put(preStr+node.c, node.children.values());
                }
            }
            preMap = tempMap;
        }
    }

    class Node {
        Map<Character, Node> children;
        boolean isEnd;
        Character c;

        Node(Character c){
            children = new HashMap<>();
            isEnd = false;
            this.c = c;
        }


    }

}
